/*
 * heap-sort
 *
 * Facts:
 * 1. heap structure is a binary tree, could be represented by an array 
 * 2. given a tree node i, its parent: (i-1)/2, left child: 2i+1, right child: 2i+2
 * 3. height of a heap containing n nodes is floor(lgn)
 * 4. when using array to represent a heap containing n nodes, the leaves begins at floor(n/2), floor(n/2)+1, ...
 */

#include<stdio.h>
#define PARENT(i) ((i-1)>>1)
#define LCHILD(i) ((i<<1)+1)
#define RCHILD(i) ((i+1)<<1)

int heapsize; /* heap nodes in array */

void 
swap(int *arr, int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

/*
 * assuming both the LeftChild and RightChild of i are already max-heap
 * T(n) = O(lgn)
 */
void
max_heapify_recursive(int *arr, int i)
{
	int left = LCHILD(i);
	int right = RCHILD(i);
	int largest = i;
	if(left<heapsize && arr[left]>arr[largest])
		largest = left;
	if(right<heapsize && arr[right]>arr[largest])
		largest = right;
	if(largest != i) {
		swap(arr, largest, i);
		max_heapify_recursive(arr, largest);
	}
}

void
max_heapify(int *arr, int i)
{
	int left, right, largest;
	while(i < (heapsize>>1)) {
		left = LCHILD(i);
		right = RCHILD(i);
		largest = i;
		if(left<heapsize && arr[left]>arr[largest])
			largest = left;
		if(right<heapsize && arr[right]>arr[largest])
			largest = right;
		if(largest != i) {
			swap(arr, largest, i);
			i = largest;
		}else
			break;
	}
}

/*
 * based on the Fact 4, and each leaf can be seen as a heap
 * T(n) = O(n)
 */
void
build_max_heap(int *arr, int length)
{
	int i;
	heapsize = length;
	for(i=(length>>1)-1; i>=0; --i)
		max_heapify(arr, i);
}

void
heap_sort(int *arr, int length)
{
	int i;
	build_max_heap(arr, length); /* build heap */
	for(i=length-1; i>=1; --i) {
		swap(arr, 0, i);
		--heapsize;
		max_heapify(arr, 0);
		/*--------test---------*/
		int j;
		for(j=0; j<heapsize; j++)
			printf("%d\t", arr[j]);
		printf("\n");
	}
}

/* ------------------------test--------------------------- */
int
main(int argc, char **argv)
{
	int arr[] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};

	heap_sort(arr, 10);

	int i;
	for(i=0; i<10; i++)
		printf("%d\t", arr[i]);
	printf("\n");
}
